package dualpointer;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

class Interval {
    int start;
    int end;
    public Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}
public class D230827 {
    // 合并区间
    // 时间：O(nlog2n)   排序的时间复杂度
    // 空间：O(1)          res 是返回的必要空间，没有使用额外的空间
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        ArrayList<Interval> res = new ArrayList<>();
        // 去除特殊情况
        if(intervals.size() == 0)
            return res;
        // 按照区间首排序, 如果区间首相同, 按照区间尾排序, 重载比较方法
        Collections.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval o1, Interval o2) {
                if (o1.start != o2.start)
                    return o1.start - o2.start;
                else
                    return o1.end - o2.end;
            }
        });
        // 放入第一个区间
        res.add(intervals.get(0));
        int size = 0;
        // 遍历后续区间，查看是否与末尾有重叠
        for(int i = 1; i < intervals.size(); i++) {
            Interval o1 = intervals.get(i);
            Interval origin = res.get(size);
            if(o1.start > origin.end) {
                res.add(o1);
                size++;
                // 区间有重叠，更新结尾 (两个区间重叠 且不全部包含在第一个区间中)
            } else if (o1.end > origin.end) {
                res.remove(size);
                Interval s = new Interval(origin.start, o1.end);
                res.add(s);
            }
        }
        return res;
    }


    //
}
